/*
day435 
2020.11.5 
*/

#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
		vector<int> res;
		if(k==0)
		{
			return res;
		}
		help(arr,res,k,0,arr.size()-1);
		return res;
    }
    
    int partition(vector<int> &arr,int l,int r)
    {
    	int tem=arr[l];
    	
    	while(l<r)
    	{
    		while(l<r && arr[r]>=tem) r--;
	    	arr[l]=arr[r];
	    	
	    	while(l<r && arr[l]<=tem) ++l;
			arr[r]=arr[l];
		}
    	
		arr[l]=tem;
		return l; 
	}
	
	void help(vector<int> &arr,vector<int> &res,int k,int l,int r)
	{
		int mid=partition(arr,l,r);
		if(mid-l+1==k)
		{
			for(int i=l;i<=mid;++i)
			{
				res.push_back(arr[i]);
			}
			return ;
		}
		
		else if(mid-l+1>k)
		{
			return help(arr,res,k,l,mid-1);
		}
		
		
		for(int i=l;i<=mid;++i)
		{
			res.push_back(arr[i]);
		}
		return help(arr,res,k-(mid-l+1),mid+1,r);
	}
};


int main()
{
	vector<int> arr={0,0,1,2,4,2,2,3,1,4};
	int k=8;
	Solution s;
	vector<int> res=s.getLeastNumbers(arr,k) ;
	for(int i=0;i<res.size();++i)
	{
		cout<<res[i]<<'\t';
	}cout<<endl;
	return 0;
 } 
